НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №7
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві.
Варіант 7
Київ 20____
Мета:
Набути навичок створення та обробки бінарних дерев.
Теоретична частина:
Дерево – це сукупність вузлів і відношень, що утворює ієрархічну структуру.
Вузол (або вершина) дерева – це математична абстракція, яка моделює абстрактні об’єкти чи об’єкти реального світу.
Вузол, як правило, має ім’я, яке називається його ключем або ідентифікатором. У вище наведеному прикладі, таким ідентифікатором є повний шлях до файлу або папки(разом з іменем).
Відношення визначають зв’язки між вершинами типу батько-дитина. Ці зв’язки називаються гілками (ребрами) дерева.
На малюнку зображено впорядковане бінарне дерево:
/
Дерево називається впорядкованим, якщо набір дітей кожного його вузла є впорядкований. Діти вузла впорядкованого дерева, як правило впорядковуються зліва на право, якщо інакший порядок окремо не зазначений. Впорядкування дерев використовується для співставлення вузлів, що не пов’язані співвідношенням типу батько-син.
У даній роботі використовується послідовний спосіб проходження дерева. Який проходить дерево за наведеною схемою:
/
Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів. Вмістом цих полів будуть відповідно:
• інформаційне поле (ключ вершини);
• службове поле (їх може бути декілька або жодного);
• покажчик на ліве піддерево;
• покажчик на праве піддерево.
Завдання до роботи:
Створити бінарне дерево та виконати завдання згідно варіанту:
Варіант
Використовуваний спосіб обходу дерева для виконання завдання
Завдання
7
Послідовний
1. Реверсувати кожен елемент дерева, тобто якщо є елемент 345, то замінюємо його на 543.
2. Визначити в якому піддереві (лівому або правому) кількість парних елементів більша. Вивести ці елементи на екран для кожного піддерева окремо.
Результати виконання лабораторної роботи:
/
Дана програма спочатку створює дерево, а далі додає елементи, щоб заповнити дерево інформацією. Потім програма проходить кожен елемент дерева та реверсує ці елементи. Також програма рахує у якому піддереві парних елементів більше та виводить ці парні елементи.
Програмний код:
public class LR7 { public static void main(String[] args) { Tree tree = new Tree(); Tree.Node root = new Tree.Node(123); System.out.println("Бінарне дерево"); System.out.println("Початкове значення дерева - " + root.value); tree.insert(root, 106); tree.insert(root, 95); tree.insert(root, 45); tree.insert(root, 101); tree.insert(root, 118); tree.insert(root, 112); tree.insert(root, 121); tree.insert(root, 95); tree.insert(root, 167); tree.insert(root, 142); tree.insert(root, 136); tree.insert(root, 153); tree.insert(root, 215); tree.insert(root, 189); tree.insert(root, 329); System.out.println("Елементи дерева:"); tree.traverseInOrder(root); System.out.println("\nЕлементи дерева після реверсування:"); tree.reverse(root); tree.traverseInOrder(root); //повертаємось до початкового вигляду tree.reverse(root); int evenLeft = tree.evenNumbers(root.left); Tree.count1=0; int evenRight = tree.evenNumbers(root.right); if(evenLeft > evenRight) System.out.println("\nУ лівій частині парних чисел більше. У лівій " + evenLeft + ", а у правій " + evenRight); else if(evenLeft < evenRight) System.out.println("\nУ правій частині парних чисел більше. У правій " + evenLeft + ", а у лівій " + evenRight); else System.out.println("\nВ обох піддеревах рівна кількість парних чисел....
